An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization

摘要

We give an O(øk · n 2) algorithm for the 1-SIDED CROSSING MINIMIZATION problem, thus showing that the problem is Fixed Parameter Tractable. The constant \phi in the running time is the golden ratio \phi=\frac{1+\sqrt{5}}{2}\approx 1.618. The constant k is the parameter of the problem: the number of allowed edge crossings.